class Solution(object):
    def winnerSquareGame(self, n):
        DP = [0] * (n + 1)
        for i in range(1,n + 1):
            max_range = int(i ** 0.5)
            if max_range ** 2 == i:
                DP[i] = 1
            else:
                flag = 0
                for j in range(1, max_range + 1):
                    if DP[i - j ** 2] == 0:
                        flag = 1
                        break
                DP[i] = flag
        return DP[-1] == 1

data = Solution()
n = 4
print(data.winnerSquareGame(n))